{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #二叉搜索树染色"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #segment-tree #binary-search-tree #array #binary-search #binary-tree #ordered-set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #线段树 #二叉搜索树 #数组 #二分查找 #二叉树 #有序集合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉搜索树染色"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "欢迎各位勇者来到力扣城，本次试炼主题为「二叉搜索树染色」。\n",
    "\n",
    "每位勇士面前设有一个**二叉搜索树**的模型，模型的根节点为 `root`，树上的各个节点值均不重复。初始时，所有节点均为蓝色。现在按顺序对这棵二叉树进行若干次操作， `ops[i] = [type, x, y]` 表示第 `i` 次操作为：\n",
    "+ `type` 等于 0 时，将节点值范围在 `[x, y]` 的节点均染蓝\n",
    "+ `type` 等于 1 时，将节点值范围在 `[x, y]` 的节点均染红\n",
    "\n",
    "请返回完成所有染色后，该二叉树中红色节点的数量。\n",
    "\n",
    "\n",
    "**注意：**\n",
    "+ 题目保证对于每个操作的 `x`、`y` 值定出现在二叉搜索树节点中\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`root = [1,null,2,null,3,null,4,null,5], ops = [[1,2,4],[1,1,3],[0,3,5]]`\n",
    ">\n",
    ">输出：`2`\n",
    ">\n",
    ">解释：\n",
    ">第 0 次操作，将值为 2、3、4 的节点染红；\n",
    ">第 1 次操作，将值为 1、2、3 的节点染红；\n",
    ">第 2 次操作，将值为 3、4、5 的节点染蓝；\n",
    ">因此，最终值为 1、2 的节点为红色节点，返回数量 2\n",
    "![image.png](https://pic.leetcode-cn.com/1649833948-arSlXd-image.png){:width=230px}\n",
    "\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`root = [4,2,7,1,null,5,null,null,null,null,6]` \n",
    ">`ops = [[0,2,2],[1,1,5],[0,4,5],[1,5,7]]`\n",
    ">\n",
    ">输出：`5`\n",
    ">\n",
    ">解释：\n",
    ">第 0 次操作，将值为 2 的节点染蓝；\n",
    ">第 1 次操作，将值为 1、2、4、5 的节点染红；\n",
    ">第 2 次操作，将值为 4、5 的节点染蓝；\n",
    ">第 3 次操作，将值为 5、6、7 的节点染红；\n",
    ">因此，最终值为 1、2、5、6、7 的节点为红色节点，返回数量 5\n",
    "![image.png](https://pic.leetcode-cn.com/1649833763-BljEbP-image.png){:width=230px}\n",
    "\n",
    "**提示：**\n",
    "+ `1 <= 二叉树节点数量 <= 10^5`\n",
    "+ `1 <= ops.length <= 10^5`\n",
    "+ `ops[i].length == 3`\n",
    "+ `ops[i][0]` 仅为 `0` or `1`\n",
    "+ `0 <= ops[i][1] <= ops[i][2] <= 10^9`\n",
    "+ `0 <= 节点值 <= 10^9`\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [QO5KpG](https://leetcode.cn/problems/QO5KpG/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [QO5KpG](https://leetcode.cn/problems/QO5KpG/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,null,2,null,3,null,4,null,5]\\n[[1,2,4],[1,1,3],[0,3,5]]', '[4,2,7,1,null,5,null,null,null,null,6]\\n[[0,2,2],[1,1,5],[0,4,5],[1,5,7]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        # 中序遍历获得节点的值\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return []\n",
    "            return dfs(node.left) + [node.val] + dfs(node.right)\n",
    "        values = dfs(root)\n",
    "        # 倒序遍历删除最新被覆盖过的节点\n",
    "        ans = 0\n",
    "        for tp, x, y in ops[::-1]:\n",
    "            i = bisect.bisect_left(values, x)\n",
    "            j = bisect.bisect_right(values, y)\n",
    "            if tp == 1:\n",
    "                ans += j-i\n",
    "            values = values[:i] + values[j:]\n",
    "            if not values:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        # 暴力解法：就是遍历二叉树，然后做染色，然后做统计\n",
    "        # 优化办法：\n",
    "        # 操作的 x,y 区间重叠，看最后的操作是什么\n",
    "        # 合并操作\n",
    "         # 中序遍历获得节点的值\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return []\n",
    "            return dfs(node.left) + [node.val] + dfs(node.right)\n",
    "        values = dfs(root)\n",
    "        del root\n",
    "\n",
    "        # 倒序遍历删除最新被覆盖过的节点\n",
    "        ans = 0\n",
    "        for tp, x, y in ops[::-1]:\n",
    "            i = bisect.bisect_left(values, x)\n",
    "            j = bisect.bisect_right(values, y)\n",
    "            if tp == 1:\n",
    "                ans += j-i\n",
    "            values = values[:i] + values[j:]\n",
    "            if not values:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import bisect\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        # 中序遍历获得节点的值\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return []\n",
    "            return dfs(node.left) + [node.val] + dfs(node.right)\n",
    "        values = dfs(root)\n",
    "\n",
    "        # 倒序遍历删除最新被覆盖过的节点\n",
    "        ans = 0\n",
    "        for tp, x, y in ops[::-1]:\n",
    "            i = bisect.bisect_left(values, x)\n",
    "            j = bisect.bisect_right(values, y)\n",
    "            if tp == 1:\n",
    "                ans += j-i\n",
    "            values = values[:i] + values[j:]\n",
    "            if not values:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                yield from dfs(node.left)\n",
    "                yield node.val\n",
    "                yield from dfs(node.right)\n",
    "\n",
    "        ans = 0        \n",
    "        nums = [num for num in dfs(root)]\n",
    "        for tp, x, y in ops[::-1]:\n",
    "            ix, iy = bisect_left(nums, x), bisect_right(nums, y) - 1\n",
    "            if ix <= iy:\n",
    "                if tp:\n",
    "                    ans += iy - ix + 1\n",
    "                nums = nums[:ix] + nums[iy + 1:]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        nodes = []\n",
    "        while root:\n",
    "            nodes.append(root)\n",
    "            root = root.left\n",
    "        nums = []\n",
    "        while nodes:\n",
    "            node = nodes.pop()\n",
    "            nums.append(node.val)\n",
    "            node = node.right\n",
    "            while node:\n",
    "                nodes.append(node)\n",
    "                node = node.left \n",
    "        \n",
    "        res = 0\n",
    "        for t, x, y in ops[::-1]:\n",
    "            i = bisect.bisect_left(nums, x)\n",
    "            j = bisect.bisect_right(nums, y)\n",
    "            if t:\n",
    "                res += j - i\n",
    "            nums = nums[:i] + nums[j:]\n",
    "            if not nums:\n",
    "                break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        def getnext(p: Optional[TreeNode]):\n",
    "            if not p:  return []\n",
    "            return getnext(p.left) + [p.val] + getnext(p.right)\n",
    "        \n",
    "        nums = getnext(root)\n",
    "        ans = 0\n",
    "        for op in ops[::-1]:\n",
    "            l = bisect.bisect_left(nums,op[1])\n",
    "            r = bisect.bisect(nums,op[2]) - 1\n",
    "            if l > r: continue \n",
    "            if op[0]==1:   ans += r - l + 1\n",
    "            nums[l:r+1] = []\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        lst=[]\n",
    "        def order(root):\n",
    "            if not root:\n",
    "                return \n",
    "            order(root.left)\n",
    "            lst.append(root.val)\n",
    "            order(root.right)\n",
    "        order(root)\n",
    "        \n",
    "        red_set=0\n",
    "        for i in ops[::-1]:\n",
    "            start,end=i[1],i[2]\n",
    "            b1=bisect_left(lst,start)\n",
    "            b2=bisect_right(lst,end)\n",
    "            if i[0]==1:\n",
    "                red_set+=b2-b1\n",
    "            lst=lst[:b1]+lst[b2:]\n",
    "        return red_set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        vals = []\n",
    "        self.get_data(root, vals)\n",
    "        ans = 0\n",
    "        for i in range(len(ops) - 1, -1, -1):\n",
    "            index0 = bisect.bisect_left(vals, ops[i][1])\n",
    "            index1 = bisect.bisect_right(vals, ops[i][2])\n",
    "            if ops[i][0] == 1:\n",
    "                ans += index1 - index0\n",
    "            vals[index0: index1] = []\n",
    "        return ans\n",
    "\n",
    "    def get_data(self, root: Optional[TreeNode], val: list):\n",
    "        if root.left:\n",
    "            self.get_data(root.left, val)\n",
    "        val.append(root.val)\n",
    "        if root.right:\n",
    "            self.get_data(root.right, val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        # nodes = []\n",
    "        # node = root\n",
    "        # nums = []\n",
    "        # while nodes or node:            \n",
    "        #     while node:\n",
    "        #         nodes.append(node)\n",
    "        #         node = node.left \n",
    "        #     node = nodes.pop()\n",
    "        #     nums.append(node.val)\n",
    "        #     node = node.right\n",
    "        # res = 0\n",
    "        # for t, x, y in ops[::-1]:\n",
    "        #     i = bisect.bisect_left(nums, x)\n",
    "        #     j = bisect.bisect_right(nums, y)\n",
    "        #     if t:\n",
    "        #         res += j - i\n",
    "        #     nums = nums[:i] + nums[j:]\n",
    "        #     if not nums:\n",
    "        #         break\n",
    "        # return res\n",
    "\n",
    "        # ------------------------------\n",
    "        def traverse(node):\n",
    "            if not node:\n",
    "                return \n",
    "            traverse(node.left)\n",
    "            nums.append(node.val)\n",
    "            traverse(node.right)\n",
    "            \n",
    "        nums = []\n",
    "        traverse(root)\n",
    "        res = 0\n",
    "        for t, x, y in ops[::-1]:\n",
    "            i = bisect.bisect_left(nums, x)\n",
    "            j = bisect.bisect_right(nums, y)\n",
    "            if t:\n",
    "                res += j - i\n",
    "            nums = nums[:i] + nums[j:]\n",
    "            if not nums:\n",
    "                break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        def f(node,x,y):\n",
    "            if not node: return None,0\n",
    "            if node.val < x:\n",
    "                node.right,res = f(node.right,x,y)\n",
    "                return node,res\n",
    "            if node.val > y:\n",
    "                node.left,res = f(node.left,x,y)\n",
    "                return node,res\n",
    "            node.left,l_res = f(node.left,x,y)\n",
    "            node.right,r_res = f(node.right,x,y)\n",
    "            res = l_res + r_res + 1\n",
    "            if not node.left: node = node.right\n",
    "            elif not node.right: node = node.left\n",
    "            elif not node.left.right:\n",
    "                node.left.right = node.right\n",
    "                node = node.left\n",
    "            elif not node.right.left:\n",
    "                node.right.left = node.left\n",
    "                node = node.right\n",
    "            else:\n",
    "                most_right = node.left\n",
    "                pre = None\n",
    "                while most_right.right: pre,most_right = most_right,most_right.right\n",
    "                pre.right = most_right.left\n",
    "                most_right.left = node.left\n",
    "                most_right.right = node.right\n",
    "                node = most_right\n",
    "            return node,res\n",
    "\n",
    "        ans = 0\n",
    "        for t,x,y in ops[::-1]:\n",
    "            root,res = f(root,x,y)\n",
    "            if t == 1: ans += res\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        values = list()\n",
    "\n",
    "        def dfs(root):\n",
    "            nonlocal values\n",
    "            if root is None:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            values.append(root.val)\n",
    "            dfs(root.right)\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "        result = 0\n",
    "        for tp, x, y in ops[::-1]:\n",
    "            i = bisect_left(values, x)\n",
    "            j = bisect_right(values, y)\n",
    "            if tp == 1:\n",
    "                result += j - i\n",
    "            values = values[:i] + values[j:]\n",
    "            if not values:\n",
    "                break\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        nodes = []\n",
    "        node = root\n",
    "        nums = []\n",
    "        while nodes or node:            \n",
    "            while node:\n",
    "                nodes.append(node)\n",
    "                node = node.left \n",
    "            node = nodes.pop()\n",
    "            nums.append(node.val)\n",
    "            node = node.right\n",
    "        res = 0\n",
    "        for t, x, y in ops[::-1]:\n",
    "            i = bisect.bisect_left(nums, x)\n",
    "            j = bisect.bisect_right(nums, y)\n",
    "            if t:\n",
    "                res += j - i\n",
    "            nums = nums[:i] + nums[j:]\n",
    "            if not nums:\n",
    "                break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def inOrder(self, root):\n",
    "        ans = []\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return \n",
    "            dfs(node.left)\n",
    "            ans.append(node.val)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        nums = self.inOrder(root)\n",
    "        ans = 0        \n",
    "        for tp, l, r in reversed(ops):\n",
    "            lpos = bisect_left(nums, l)\n",
    "            rpos = bisect_left(nums, r+1)\n",
    "            if tp:\n",
    "                ans += rpos - lpos\n",
    "            nums[lpos:rpos] = []\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import Counter, namedtuple\n",
    "nd=namedtuple('nd',list('lrmi'))\n",
    "class SegTree:\n",
    "    def __init__(self,a):\n",
    "        self.a=a  # 离散化,a数组中的点间隔很大,区间[i,j]表示a[i]...a[j]\n",
    "        self.n=len(a) # a[0] 空出来占位\n",
    "        self.sums=[0]*self.n*4\n",
    "        self.adds=[-999]*self.n*4  # 绝对标记-999\n",
    "    def getchildren(self,nd0):\n",
    "        return nd(nd0.l,nd0.m,(nd0.l+nd0.m)//2,nd0.i<<1), nd(nd0.m+1,nd0.r,(nd0.m+1+nd0.r)//2,nd0.i<<1|1)\n",
    "    def pushup(self,nd0):\n",
    "        self.sums[nd0.i]=self.sums[nd0.i<<1]+self.sums[nd0.i<<1|1]\n",
    "    def pushdn(self,nd0):\n",
    "        if self.adds[nd0.i] != -999:\n",
    "            nd1,nd2=self.getchildren(nd0)\n",
    "            self.adds[nd1.i]=self.adds[nd0.i]\n",
    "            self.adds[nd2.i]=self.adds[nd0.i]\n",
    "            self.sums[nd1.i]=self.adds[nd0.i]*(nd0.m-nd0.l+1)\n",
    "            self.sums[nd2.i]=self.adds[nd0.i]*(nd0.r-nd0.m)\n",
    "            self.adds[nd0.i]=-999\n",
    "    def build(self,nd0):\n",
    "        if nd0.l==nd0.r:  # 无子节点\n",
    "            self.sums[nd0.i]=self.a[nd0.l]\n",
    "            return\n",
    "        nd1,nd2=self.getchildren(nd0)\n",
    "        self.build(nd1)\n",
    "        self.build(nd2)\n",
    "        self.pushup(nd0)\n",
    "    def update_point(self,L,C,nd0):\n",
    "        if nd0.l==nd0.r:  # 无子节点\n",
    "            self.sums[nd0.i]+=C\n",
    "            return\n",
    "        nd1,nd2=self.getchildren(nd0)\n",
    "        self.update_point(L,C,nd1 if L<=nd0.m else nd2)\n",
    "        self.pushup(nd0)\n",
    "    def update(self,L,R,C,nd0): # 绝对更新标记, [L,R]的值都置为C\n",
    "        if L<=nd0.l and nd0.r<=R:\n",
    "            self.sums[nd0.i]=(nd0.r-nd0.l+1)*C  # (R-L+1)*C\n",
    "            self.adds[nd0.i]=C\n",
    "            return\n",
    "        self.pushdn(nd0)\n",
    "        nd1,nd2=self.getchildren(nd0)\n",
    "        if L<=nd0.m:\n",
    "            self.update(L,R,C,nd1)\n",
    "        if R>=nd0.m+1:\n",
    "            self.update(L,R,C,nd2)\n",
    "        self.pushup(nd0)\n",
    "    def query(self,L,R,nd0):\n",
    "        if L<=nd0.l and nd0.r <=R:\n",
    "            return self.sums[nd0.i]\n",
    "        self.pushdn(nd0)\n",
    "        ans=0\n",
    "        nd1,nd2=self.getchildren(nd0)\n",
    "        if L<=nd0.m:\n",
    "            ans+=self.query(L,R,nd1)\n",
    "        if R>=nd0.m+1:\n",
    "            ans+=self.query(L,R,nd2)\n",
    "        return ans\n",
    "class FenwickTree:\n",
    "    lowbit = lambda x: x&(-x)\n",
    "    def __init__(self,c):\n",
    "        self.c=c\n",
    "    def add(self,x,delta):\n",
    "        while x<len(self.c):\n",
    "            self.c[x]+=delta\n",
    "            x+=FenwickTree.lowbit(x)\n",
    "    def get(self,x):\n",
    "        ans = 0\n",
    "        while x:\n",
    "            ans+=self.c[x]\n",
    "            x-=FenwickTree.lowbit(x)\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    # _lazy\n",
    "    def getNumber_lazy(self, root: Optional[TreeNode], ops: List[List[int]]):\n",
    "        nds = []\n",
    "        def dfs(nd):\n",
    "            if not nd:\n",
    "                return\n",
    "            dfs(nd.left)\n",
    "            nds.append(nd.val)\n",
    "            dfs(nd.right)\n",
    "        dfs(root)\n",
    "        n=len(nds)\n",
    "        d={k:i for i,k in enumerate(nds,1)}\n",
    "        # print([d[c] for c in nums])\n",
    "        t=SegTree([0]*(n+1))\n",
    "        nd0=nd(1,n,(1+n)//2,1)\n",
    "        res=0\n",
    "        # for i,c in enumerate(nums,1):\n",
    "        for tp,x,y in (ops):\n",
    "            t.update(d[x],d[y],tp,nd0)\n",
    "        res+=(t.query(1,n,nd0))\n",
    "        return res\n",
    "    # easy\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        # rrrbbbbbrrrrbbbrrr\n",
    "        # 逆序遍历, 选中的区间部分都剪切下来\n",
    "        nds = []\n",
    "        def dfs(nd):\n",
    "            if not nd:\n",
    "                return\n",
    "            dfs(nd.left)\n",
    "            nds.append(nd.val)\n",
    "            dfs(nd.right)\n",
    "        dfs(root)\n",
    "        # print(nds)\n",
    "        res=0\n",
    "        for t,x,y in reversed(ops):\n",
    "            t1 = bisect_left(nds, x)\n",
    "            t2 = bisect_right(nds, y)  # 1 5 9 各个节点值均不重复\n",
    "            if t:\n",
    "                res+=(t2-t1)\n",
    "            nds=nds[:t1]+nds[t2:]  # 选中的区间部分都剪切下来\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "def lower_bound(nums, target):\n",
    "    l = 0\n",
    "    r = len(nums) - 1\n",
    "    while l <= r:\n",
    "        mid = (l + r) // 2\n",
    "        if nums[mid] < target:\n",
    "            l = mid + 1\n",
    "        else:\n",
    "            r = mid - 1\n",
    "    return l\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        def mid_travel(root, res):\n",
    "            if not root:\n",
    "                return\n",
    "            mid_travel(root.left, res)\n",
    "            res.append(root.val)\n",
    "            mid_travel(root.right, res)\n",
    "        \n",
    "        nums = []\n",
    "        mid_travel(root, nums)\n",
    "        # print(nums)\n",
    "        res = 0\n",
    "        # print(ops[-1][1])\n",
    "        # lower = lower_bound(nums, ops[-1][1])\n",
    "        # print(lower)\n",
    "        for op in ops[::-1]:\n",
    "            lower = lower_bound(nums, op[1])\n",
    "            upper = lower_bound(nums, op[2]+1) - 1\n",
    "            if lower > upper:\n",
    "                continue\n",
    "            if op[0] == 1:\n",
    "                res += upper - lower + 1\n",
    "            nums[lower:upper+1] = []\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def inOrder(self, root):\n",
    "        ans = []\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return \n",
    "            dfs(node.left)\n",
    "            ans.append(node.val)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        nums = self.inOrder(root)\n",
    "        ans = 0        \n",
    "        for tp, l, r in reversed(ops):\n",
    "            lpos = bisect_left(nums, l)\n",
    "            rpos = bisect_right(nums, r)\n",
    "            if tp:\n",
    "                ans += rpos - lpos\n",
    "            nums[lpos:rpos] = []\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        li = []\n",
    "        dic = {}\n",
    "        ans = 0\n",
    "        def pre_que(node):\n",
    "            if node:\n",
    "                li.append(node.val)\n",
    "                pre_que(node.left)\n",
    "                pre_que(node.right)\n",
    "        pre_que(root)\n",
    "        li.sort()\n",
    "        for i in li:\n",
    "            dic[i] = 0\n",
    "        for i in ops[::-1]:\n",
    "            b1 = bisect_left(li,i[1])\n",
    "            b2 = bisect_right(li,i[2])\n",
    "            if i[0] == 1:\n",
    "                ans += b2-b1\n",
    "            li = li[:b1]+li[b2:]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 0\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        ops = list(reversed(ops))\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            for t, x, y in ops:\n",
    "                if t == 1 and x <= root.val and root.val <= y:\n",
    "                    self.ans += 1\n",
    "                    break\n",
    "                if t == 0 and x <= root.val and root.val <= y:\n",
    "                    break\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedDict\n",
    "\n",
    "class RangeModule:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.intervals = SortedDict()\n",
    "\n",
    "    def addRange(self, left: int, right: int) -> None:\n",
    "        intervals = self.intervals\n",
    "        \n",
    "        x = intervals.bisect_right(left)\n",
    "        if x != 0:\n",
    "            start = x - 1\n",
    "            if intervals.values()[start] >= right:\n",
    "                return \n",
    "\n",
    "            if intervals.values()[start] >= left:\n",
    "                left = intervals.keys()[start]\n",
    "                intervals.popitem(start)\n",
    "\n",
    "                x -= 1\n",
    "\n",
    "        while x < len(intervals) and intervals.keys()[x] <= right:\n",
    "            right = max(right, intervals.values()[x])\n",
    "            intervals.popitem(x)\n",
    "\n",
    "        intervals[left] = right\n",
    "\n",
    "    def queryRange(self, left: int, right: int) -> bool:\n",
    "        intervals = self.intervals\n",
    "\n",
    "        x = intervals.bisect_right(left)\n",
    "        if x == 0:\n",
    "            return False\n",
    "\n",
    "        return right <= intervals.values()[x - 1]\n",
    "\n",
    "    def removeRange(self, left: int, right: int) -> None:\n",
    "        intervals = self.intervals\n",
    "\n",
    "        x = intervals.bisect_right(left)\n",
    "        if x != 0:\n",
    "            start = x - 1\n",
    "            if (r := intervals.values()[start]) >= right:\n",
    "                if (l := intervals.keys()[start]) == left:\n",
    "                    intervals.popitem(start)\n",
    "                else:\n",
    "                    intervals[l] = left\n",
    "\n",
    "                if right != r:\n",
    "                    intervals[right] = r\n",
    "\n",
    "                return\n",
    "            elif r > left:\n",
    "                intervals[intervals.keys()[start]] = left\n",
    "\n",
    "        while x < len(intervals) and intervals.keys()[x] < right:\n",
    "            if intervals.values()[x] <= right:\n",
    "                intervals.popitem(x)\n",
    "            else:\n",
    "                intervals[right] = intervals.values()[x]\n",
    "                intervals.popitem(x)\n",
    "\n",
    "                break\n",
    "\n",
    "\n",
    "\n",
    "# Your RangeModule object will be instantiated and called as such:\n",
    "# obj = RangeModule()\n",
    "# obj.addRange(left,right)\n",
    "# param_2 = obj.queryRange(left,right)\n",
    "# obj.removeRange(left,right)\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        \n",
    "        def dfs(root: TreeNode, rm: RangeModule) -> int:\n",
    "            if root is None:\n",
    "                return 0\n",
    "\n",
    "            val = rm.queryRange(root.val, root.val + 1)\n",
    "            left = dfs(root.left, rm)\n",
    "            right = dfs(root.right, rm)\n",
    "\n",
    "            return val + left + right\n",
    "\n",
    "        rm = RangeModule()\n",
    "        for op, x, y in ops:\n",
    "            if op == 0:\n",
    "                rm.removeRange(x, y + 1)\n",
    "            else:\n",
    "                rm.addRange(x, y + 1)\n",
    "\n",
    "        return dfs(root, rm)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        def f(node,x,y):\n",
    "            if not node: return None,0\n",
    "            if node.val < x:\n",
    "                node.right,res = f(node.right,x,y)\n",
    "                return node,res\n",
    "            if node.val > y:\n",
    "                node.left,res = f(node.left,x,y)\n",
    "                return node,res\n",
    "            node.left,l_res = f(node.left,x,y)\n",
    "            node.right,r_res = f(node.right,x,y)\n",
    "            res = l_res + r_res + 1\n",
    "            if not node.left: node = node.right\n",
    "            elif not node.right: node = node.left\n",
    "            elif not node.left.right:\n",
    "                node.left.right = node.right\n",
    "                node = node.left\n",
    "            elif not node.right.left:\n",
    "                node.right.left = node.left\n",
    "                node = node.right\n",
    "            else:\n",
    "                most_right = node.left\n",
    "                pre = None\n",
    "                while most_right.right: pre,most_right = most_right,most_right.right\n",
    "                pre.right = most_right.left\n",
    "                most_right.left = node.left\n",
    "                most_right.right = node.right\n",
    "                node = most_right\n",
    "            return node,res\n",
    "\n",
    "        ans = 0\n",
    "        for t,x,y in ops[::-1]:\n",
    "            root,res = f(root,x,y)\n",
    "            if t == 1: ans += res\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedDict\n",
    "\n",
    "class RangeModule:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.intervals = SortedDict()\n",
    "\n",
    "    def addRange(self, left: int, right: int) -> None:\n",
    "        intervals = self.intervals\n",
    "        \n",
    "        x = intervals.bisect_right(left)\n",
    "        if x != 0:\n",
    "            start = x - 1\n",
    "            if intervals.values()[start] >= right:\n",
    "                return \n",
    "\n",
    "            if intervals.values()[start] >= left:\n",
    "                left = intervals.keys()[start]\n",
    "                intervals.popitem(start)\n",
    "\n",
    "                x -= 1\n",
    "\n",
    "        while x < len(intervals) and intervals.keys()[x] <= right:\n",
    "            right = max(right, intervals.values()[x])\n",
    "            intervals.popitem(x)\n",
    "\n",
    "        intervals[left] = right\n",
    "\n",
    "    def queryRange(self, left: int, right: int) -> bool:\n",
    "        intervals = self.intervals\n",
    "\n",
    "        x = intervals.bisect_right(left)\n",
    "        if x == 0:\n",
    "            return False\n",
    "\n",
    "        return right <= intervals.values()[x - 1]\n",
    "\n",
    "    def removeRange(self, left: int, right: int) -> None:\n",
    "        intervals = self.intervals\n",
    "\n",
    "        x = intervals.bisect_right(left)\n",
    "        if x != 0:\n",
    "            start = x - 1\n",
    "            if (r := intervals.values()[start]) >= right:\n",
    "                if (l := intervals.keys()[start]) == left:\n",
    "                    intervals.popitem(start)\n",
    "                else:\n",
    "                    intervals[l] = left\n",
    "\n",
    "                if right != r:\n",
    "                    intervals[right] = r\n",
    "\n",
    "                return\n",
    "            elif r > left:\n",
    "                intervals[intervals.keys()[start]] = left\n",
    "\n",
    "        while x < len(intervals) and intervals.keys()[x] < right:\n",
    "            if intervals.values()[x] <= right:\n",
    "                intervals.popitem(x)\n",
    "            else:\n",
    "                intervals[right] = intervals.values()[x]\n",
    "                intervals.popitem(x)\n",
    "\n",
    "                break\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        \n",
    "        def dfs(root: TreeNode, robj: RangeModule) -> int:\n",
    "            if root is None:\n",
    "                return 0\n",
    "\n",
    "            val = robj.queryRange(root.val, root.val + 1)\n",
    "            left = dfs(root.left, robj)\n",
    "            right = dfs(root.right, robj)\n",
    "\n",
    "            return val + left + right\n",
    "\n",
    "        robj = RangeModule()\n",
    "        for op, x, y in ops:\n",
    "            if op == 0:\n",
    "                robj.removeRange(x, y + 1)\n",
    "            else:\n",
    "                robj.addRange(x, y + 1)\n",
    "\n",
    "        return dfs(root, robj)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left, bisect_right\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        val_list = []\n",
    "\n",
    "        def helper(node):\n",
    "            if node:\n",
    "                helper(node.left)\n",
    "                val_list.append(node.val)\n",
    "                helper(node.right)\n",
    "\n",
    "        helper(root)\n",
    "        count = 0\n",
    "        for typ, start, end in ops[::-1]:\n",
    "            start_index = bisect_left(val_list, start)\n",
    "            end_index = bisect_right(val_list, end) - 1\n",
    "            if typ == 1:\n",
    "                count += end_index - start_index + 1\n",
    "            val_list[start_index: end_index + 1] = []\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "\n",
    "        def inorder(root: TreeNode) -> None:\n",
    "            if root is None:\n",
    "                return \n",
    "\n",
    "            nonlocal nums\n",
    "\n",
    "            inorder(root.left)\n",
    "            nums.append(root.val)\n",
    "            inorder(root.right)\n",
    "\n",
    "        nums = []\n",
    "        inorder(root)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for op, x, y in ops[::-1]:\n",
    "            left = bisect_left(nums, x)\n",
    "            right = bisect_right(nums, y)\n",
    "            \n",
    "            if left >= right:\n",
    "                continue\n",
    "            \n",
    "            if op == 1:\n",
    "                res += right - left\n",
    "\n",
    "            nums[left: right] = []\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "\n",
    "        def inorder(root: TreeNode) -> None:\n",
    "            if root is None:\n",
    "                return \n",
    "\n",
    "            nonlocal nums\n",
    "\n",
    "            inorder(root.left)\n",
    "            nums.append(root.val)\n",
    "            inorder(root.right)\n",
    "\n",
    "        nums = []\n",
    "        inorder(root)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for op, x, y in ops[::-1]:\n",
    "            left = bisect_left(nums, x)\n",
    "            right = bisect_right(nums, y) - 1\n",
    "            \n",
    "            if left > right:\n",
    "                continue\n",
    "            \n",
    "            if op == 1:\n",
    "                res += right - left + 1\n",
    "\n",
    "            nums[left: right + 1] = []\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Tree:\n",
    "    tag = []\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.tag = [0] * (4 * n + 7)\n",
    "\n",
    "    def push_down(self, rt):\n",
    "        self.tag[rt << 1] = self.tag[rt << 1 | 1] = self.tag[rt]\n",
    "        self.tag[rt] = 0\n",
    "\n",
    "    def update(self, l, r, v, ll, rr, rt):\n",
    "        if l <= ll and rr <= r:\n",
    "            self.tag[rt] = v\n",
    "            return\n",
    "        m = (ll + rr) // 2\n",
    "        if self.tag[rt] != 0: self.push_down(rt)\n",
    "        if m >= l: self.update(l, r, v, ll, m, rt << 1)\n",
    "        if m < r: self.update(l, r, v, m + 1, rr, rt << 1 | 1)\n",
    "\n",
    "    def get(self, l, r, ll, rr, rt):\n",
    "        if l <= ll and rr <= r: return self.tag[rt]\n",
    "        if self.tag[rt] != 0: self.push_down(rt)\n",
    "        m = (ll + rr) // 2\n",
    "        if m >= l: return self.get(l, r, ll, m, rt << 1)\n",
    "        if m < r: return self.get(l, r, m + 1, rr, rt << 1 | 1)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        nums = []\n",
    "\n",
    "        def dfs(rt):\n",
    "            if rt is None: return\n",
    "            dfs(rt.left)\n",
    "            nums.append(rt.val)\n",
    "            dfs(rt.right)\n",
    "\n",
    "        dfs(root)\n",
    "        n = len(nums)\n",
    "        idx = {j: i + 1 for i, j in enumerate(nums)}\n",
    "        tree = Tree(n)\n",
    "        for op, x, y in ops:\n",
    "            op = -1 if op == 0 else op\n",
    "            tree.update(idx[x], idx[y], op, 1, n, 1)\n",
    "        ret = 0\n",
    "        for i in nums:\n",
    "            if tree.get(idx[i], idx[i], 1, n, 1) == 1:\n",
    "                ret += 1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from  sortedcontainers import SortedSet\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        nodes = SortedSet()\n",
    "        st = deque([root])\n",
    "        while st:\n",
    "            nod = st.popleft()\n",
    "            nodes.add(nod.val)\n",
    "            if nod.left:\n",
    "                st.append(nod.left)\n",
    "            if nod.right:\n",
    "                st.append(nod.right)\n",
    "\n",
    "        ans = 0 \n",
    "        for i in range(len(ops)-1, -1, -1):\n",
    "            while True:\n",
    "                it = nodes.bisect_left(ops[i][1])\n",
    "                if it==len(nodes) or nodes[it]>ops[i][2]:\n",
    "                    break \n",
    "                nodes.discard(nodes[it])\n",
    "                if ops[i][0]:\n",
    "                    ans += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        \n",
    "        def dfs(root):\n",
    "            if not root: return []\n",
    "            return dfs(root.left) + [root.val] + dfs(root.right)\n",
    "        s = dfs(root)\n",
    "        ans = 0\n",
    "        for ty, x, y in reversed(ops):\n",
    "            i = bisect_left(s, x)\n",
    "            j = bisect_right(s, y)\n",
    "            if ty == 1:\n",
    "                ans += j - i \n",
    "            s = s[:i] + s[j:]\n",
    "            if not s: break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Optional\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def getNumber(self, root: TreeNode, ops: List[List[int]]) -> int:\n",
    "        N = 10**9 + 1\n",
    "        seg = {0: 1, N: 0}\n",
    "        \n",
    "        def cut(i):\n",
    "            if i < 0 or i > N:\n",
    "                return\n",
    "            if i not in seg:\n",
    "                it = next((x for x in reversed(sorted(seg.keys())) if x < i), None)\n",
    "                seg[i] = seg[it]\n",
    "        \n",
    "        for op in ops:\n",
    "            t, x, y = op[0] + 1, op[1], op[2]\n",
    "            cut(x)\n",
    "            cut(y + 1)\n",
    "            \n",
    "            keys_to_remove = [k for k in seg if x < k <= y]\n",
    "            for k in keys_to_remove:\n",
    "                del seg[k]\n",
    "            \n",
    "            seg[x] = t\n",
    "            if seg.get(y + 1) == seg[x]:\n",
    "                del seg[y + 1]\n",
    "            \n",
    "            if x > 0:\n",
    "                keys = sorted(seg.keys())\n",
    "                idx = keys.index(x)\n",
    "                if seg[keys[idx]] == seg[keys[idx-1]]:\n",
    "                    del seg[keys[idx]]\n",
    "        \n",
    "        ans = 0\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return\n",
    "            v = node.val\n",
    "            it = next((x for x in reversed(sorted(seg.keys())) if x <= v), None)\n",
    "            if seg[it] == 2:\n",
    "                ans += 1\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                yield from dfs(node.left)\n",
    "                yield node.val\n",
    "                yield from dfs(node.right)\n",
    "            \n",
    "        nums = [num for num in dfs(root)]\n",
    "        ans = 0\n",
    "        for tp, x, y in ops[::-1]:\n",
    "            n_nums = []\n",
    "            for num in nums:\n",
    "                if num >= x and num <= y:\n",
    "                    if tp == 1:\n",
    "                        ans += 1\n",
    "                else:\n",
    "                    n_nums.append(num)\n",
    "            nums = n_nums\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self, n):\n",
    "        self.vals = [0] * (4 * n)\n",
    "        self.lazy = [-1] * (4 * n)\n",
    "\n",
    "    def range_modify(self, idx, start, end, ql, qr, val):\n",
    "        mid = (start + end) >> 1\n",
    "        if ql <= start <= end <= qr:\n",
    "            self.vals[idx] = (end - start + 1) * val\n",
    "            self.lazy[idx] = val\n",
    "        else:\n",
    "            left_child, right_child = idx << 1, (idx << 1) + 1\n",
    "            if self.lazy[idx] != -1:\n",
    "                lazy = self.lazy[idx]\n",
    "                self.vals[left_child] = (mid - start + 1) * lazy\n",
    "                self.lazy[left_child] = lazy\n",
    "                self.vals[right_child] = (end - mid) * lazy\n",
    "                self.lazy[right_child] = lazy\n",
    "                self.lazy[idx] = -1\n",
    "            if ql <= mid:\n",
    "                self.range_modify(left_child, start, mid, ql, min(mid, qr), val)\n",
    "            if mid + 1 <= qr:\n",
    "                self.range_modify(right_child, mid + 1, end, max(mid + 1, ql), qr, val)\n",
    "            self.lazy[idx] = -1\n",
    "            self.vals[idx] = self.vals[left_child] + self.vals[right_child]\n",
    "\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        i = 1\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal i\n",
    "            if node is None:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            d[node.val] = i\n",
    "            i += 1\n",
    "            dfs(node.right)\n",
    "\n",
    "        d = dict()\n",
    "        dfs(root)\n",
    "        n = i - 1\n",
    "        seg_tree = SegTree(n)\n",
    "        for op, x, y in ops:\n",
    "            l, r = d[x], d[y]\n",
    "            seg_tree.range_modify(1, 1, n, l, r, op)\n",
    "        return seg_tree.vals[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self, n):\n",
    "        self.vals = [0] * (4 * n)\n",
    "        self.lazy = [-1] * (4 * n)\n",
    "\n",
    "    def range_modify(self, idx, start, end, ql, qr, val):\n",
    "        mid = (start + end) >> 1\n",
    "        if ql <= start <= end <= qr:\n",
    "            self.vals[idx] = (end - start + 1) * val\n",
    "            self.lazy[idx] = val\n",
    "        else:\n",
    "            left_child, right_child = idx << 1, (idx << 1) + 1\n",
    "            if self.lazy[idx] != -1:\n",
    "                lazy = self.lazy[idx]\n",
    "                self.vals[left_child] = (mid - start + 1) * lazy\n",
    "                self.lazy[left_child] = lazy\n",
    "                self.vals[right_child] = (end - mid) * lazy\n",
    "                self.lazy[right_child] = lazy\n",
    "                self.lazy[idx] = -1\n",
    "            if start <= ql <= mid:\n",
    "                self.range_modify(left_child, start, mid, ql, min(mid, qr), val)\n",
    "            if mid + 1 <= qr <= end:\n",
    "                self.range_modify(right_child, mid + 1, end, max(mid + 1, ql), qr, val)\n",
    "            self.lazy[idx] = -1\n",
    "            self.vals[idx] = self.vals[left_child] + self.vals[right_child]\n",
    "\n",
    "class Solution:\n",
    "    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:\n",
    "        i = 1\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal i\n",
    "            if node is None:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            d[node.val] = i\n",
    "            i += 1\n",
    "            dfs(node.right)\n",
    "\n",
    "        d = dict()\n",
    "        dfs(root)\n",
    "        n = i - 1\n",
    "        seg_tree = SegTree(n)\n",
    "        for op, x, y in ops:\n",
    "            l, r = d[x], d[y]\n",
    "            seg_tree.range_modify(1, 1, n, l, r, op)\n",
    "        return seg_tree.vals[1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
